Hello, everyone, welcome back to the Heterogeneous Parallel Programming class.
This is lecture 1.4, Introduction to CUDA, and we're
going to be talking about Data Parallelism and Threads.
The objective of this lecture is to help you
to learn about data parallelism and the basic features of
CUDA C, which is a heterogeneous parallel programming interface that enables the
exploitation of data parallelism by using both CPUs and GPUs.
And, the topics that we're going to
cover today are the hierarchical thread organization,
the main interfaces for launching parallel execution,
and the thread index to data index mapping.
The phenomena of data parallelism is that, different parts of the data can actually
be processed independently of each other. A very simple example is vector addition.
When we add two vectors together,
the elements can be added together independently.
A[0] and B[0] can be added into, to form C[0]
and A[1] and B[1] can added to form C[1] independently
of each other.
So, if we have a large number of elements in each vectors, and, we have a
large amount of hardware, we should be able
to eh, to perform all these additions in parallel.
And that's how we can fundamentally,
achieve high performance in a, CUDA, program.
So that's the reason why we're going to be using
this very simple example to illustrate the basic concepts of CUDA.
The execute, parallel execution model of CUDA and its close relative Open CL
are both based on a host plus device kind of, arrangement.
So, the, the basic concept is that when we start executing a piece of
code or application, the application will be executing on the host.
The host is typically a CPU core.
And when we start to, to, execute into a parallel part of the application, that's
when we, we start to have an opportunity to, to use a throughput oriented, device.
So this is done by writing
some specialized functions called kernel functions.
These kernel functions are very similar
to, functions in the C programming language.
They also take parameters or arguments. So that's why I showed that,
for a kernel function called KernelA, it will take arguments
just like the C functions. However, they also take configuration
parameters and, these configuring parameters are specially noted
by three less signs in the front and three greater-than signs in
the back.
In between, it gives the, a configuration parameter of number of thread
blocks, in the grid and number of threads in a thread block.
So in this, example on the right hand side, we show that the, the kernel will be
executed by a number of thread blocks which
are shown as rectangular blocks with, each with several
threads in them.
And then, within each thread block, we will
have a number of threads, all executing in parallel.
So then, after the execution of the kernel function, we will return to a sequential
execution, sequential part of the application, so
we return to the host for sequential execution.
And then, while we reach another part of the application
where we have an opportunity, we write
another KernelB that can be executed in parallel.
So the execution will go between host and
device, device in CUDA means parallel execution device.
And, most of the time, the device are, correspond to throughput-oriented GPUs.
This picture shows a, the levels of attraction in a computer system.
When we, typically, when we have an application,
the application solves a problem at the human level.
So we will have natural language description of the
problems that, that the application should be, should solve.
And then, based on the description of the problem, we can,
we'll define algorithms which have very well-defined steps of
computation and a well defined criteria for terminating the computation.
And then the algorithms will be implemented with, programming
languages such as C and C++ and so on.
CUDA is really a programming language at the C level.
And it's actually
designed as an extension to the C language.
And, more recently, more and more of the C++ features are also available in CUDA.
So CUDA is becoming more and more of a C++ programming language extension.
However, in order to fully understand the behavior of the CUDA
programs, often I will have to go a little bit lower into
the abstraction layers and look at
the instruction set architecture and micro-architecture,
which is the organization of hardware to be able to, to execute programs.
And, so therefore, we're going to actually go down a little bit in today's lecture,
just so that, you can have a
solid understanding of the execution model of CUDA.
And this is, based on a,
a picture from Patt and Patel, Introduction to Computing
Systems from Bits to Bytes, and To Gates and Beyond.
Let's go a little bit into the concept of ISA or Instruction Set Architecture.
And the Instruction Set Architecture is a contract between hardware and software.
Mostly, the Instruction Set Architecture, specifies a
set of instructions that the hardware can execute.
As long as the software consists of these
instructions, the hardware knows what to do, according for
each, for the software. So whenever we write a piece of code in
CUDA, it will eventually be compiled down to the Instruction Set Architecture level.
And the program is, the program is said to be at the Instructions Set level whenever
it is compiled down to these instructions. At this level a program is really
a set of instructions stored in memory that
can be read, interpreted, and executed by the hardware.
But program instructions will then operate on the data
that are stored in memory or provided by input/output devices.
The next slides shows a, very simplified diagram of how the hardware is
typically organized to execute programs that are
represented at the Instruction Set Architecture level.
And this diagram is
really based on Von-Neumann Processor model, which was
proposed by John von Neumann in the 1940s.
Today, virtually all the processor cores are designed
based on this or variations of this particular model.
So let's start with the bottom.
The bottom here shows the Control Unit and the Control Unit contains a
program counter and the instruction register.
The program counter essentially specifies the location in memory where the hardware
can find the next instruction that should be executed for the application.
So, there is a dash line going from the control unit to the memory essentially
that this, the, the communication pass for the control unit to deliver
the PC value to the memory and demand the memory to, to return the instruction bits.
Once the instruction bits return from the memory,
it will be placed into instruction register, or IR.
That's where the hardware will examine all the instruction bits and determine
all the activities that need to happen in order to execute that instruction.
And these activities are actually coordinated by the
control signals, which are represented with the, by
the dashed line going from control unit to
the processing unit in the middle of the picture.
This, these control signals essentially define the
activities that the ALU, the register file,
and other components in the com-, the processing unit need to, need to take in
every clock cycle in order to execute the instruction.
And, during the execution, some of the instructions will need to be
able to access data, read or write data from or to memory.
And that's, indicated by the upward arrow and the downward
arrow of the, between the processing unit and the memory.
So,
depending on the type of instruction, the, the execution will have activities
in ALUs and register files and, and accessing memory and so on.
Finally, some of the data will be moved
back and forth between the memory and the I/O.
The I/O represents the network and the disks
and so on, and the displays and so on.
So the
data will be moved back and forth between memory and I/O.
And so we're actually going to see a little bit
of I/O activity as well for the rest of the class.
So now we are ready to talk about more specifics about a, of a CUDA thread.
A CUDA thread is really a virtualized or abstracted Von-Neumann processor.
You can think about every CUDA thread as one of these processors
and these, each of these processors will be able to execute a program.
So the kernel
function that we describe is that program.
And the hardware will actually generate
a large number of these Von-Neumann processors,
and each of them will, hardware provides
a large number of these Von-Neumann processors.
And each of these processors will
be executing that function, the kernel function.
So,
but it's virtualized in the sense that, if
you look at the hardware, the number of real
processors may be much, much smaller than the
threads that a CUDA program will pro, will create.
So a lot of these threads will actually need
to be, to be executed by the real processor.
In turn. So some of them will
be actively executing and some of them will not be actively executing, and this
is what we call context switching, and that will be, it, we'll
elaborate on that very soon in one of the future lectures.
So let's go into the way a CUDA
programmer think about threads. So whenever a
CUDA kernel is executed, it's executed by a grid or array
of threads. So here we show a one-dimensional,
thread block. And let's say, let's assume
for the moment that the grid has only one thread block for this, for the moment.
So all the threads would, actually, run the same
code as we described before, but every thread will have
a different index value, or thread index value, that it
will use to compute memory addresses and make controlled decisions.
In this particular example, we show that
there are 256 threads in the third block.
And each of them will have a unique thread index from 0 to 255.
And there's a piece of code that, in the kernel, that I'm
showing in the, in the, box underneath, and that box is
first calculates a i variable based on the thread index.
This i variable
is actually private to every thread, that is, every processor, Von-Neumann
processor that correspond to those threads will have a unique i variable.
Thread ID, thread 0 will have its own i, thread 1 will have its own i and so on.
Thread 0 will calculate its i value as 0 in this case because
the thread index on x value for thread 0 is 0, so i will be 0 in this case,
for thread 0. Thread 2 will have i value
2 and so on. And thread 255 will have i value 255.
So, when we execute the statement, C[i] equals A[i] plus B[i],
the i value for every thread will be different.
So thread 0 will be adding A[0] plus B[0] and assign that to C[0].
And thread 255 will be adding A[255] plus
B[255] and assign that to C[255].
Now that we understand how a single thread
block works, we can now expand to multiple thread blocks.
Here we show a grid of threads that are organized into n thread blocks.
And each thread block still consists of 256 threads.
So, here, every thread not only have a thread index, but also a block index.
The block index variable is called blockidx.x.
The thread index is called threadidx.x.
These are predefined CUDA variables that we can use in a
kernel, and they actually are initialized by the hardware for each thread.
So you don't need to initialize these variables
because the system initializes these variables for every thread.
Now,
when we formed a data index, now we need to
factor in both the thread index and the, block index.
So in order to calculate i, now we, we take the block
index and multiply that by the block dimension, in this case, 256.
And then we add it to the thread index, so the,
thread 0 in, in block 0 still has
i value 0, because the block index is, value is 0 in this
case. So, but if we look at, thread
block 1, now all the threads are going to be seeing
thread blockidx.x value 256.
So thread 0 in block 1 will actually have a i
value of 256 instead of 0. And
then, obviously, the next thread block, thread 0 in thread block 2,
will have for the i value of 512.
So this is the, as a result, the i values
of the first thread block will range from 0 to
255. And all the i values from thread
block 1 will range from 256 to
511. As you can see, now all the threads
form a uniform coverage of all the array elements.
0 to 255 in the first thread block and then
256 on to 511 in the next thread block,
and 512 to, 780, 60,
67 in the next, block.
So, you wish, this kind of coverage is what we call a linear
coverage of a one-dimensional array. By using this formula, we can make
sure that every element of A, B, and C is covered by one of the threads.
In reality, we maybe, have, each thread to cover more than one element
and we will come back to this point, but at, at, a later point.
But, at this point, it's sufficient to understand how,
just how we can map every thread to a unique, array index, array element.
So, the threads within a thread block can actually
cooperate through sheer memory, atomic operations, and barrier synchronization.
At this point, it's sufficient for you to just be,
familiar with these three terms, because we are
going to actually go into much more detail.
Essentially, shared memory allows the threads to exchange data, the atomic
operations allow the threads to be able to coordinate their updates
to the same variables and the barrier synchronization allow the threads
to, to force each other, to force others to wait for them.
So all these activities
allow a coordination of activities across different
threads. However, threads in different blocks do
not interact. So thread 0 through 255 in thread
block 0 cannot interact with the threads
0-256 in thread block 1. There's no real
interaction that we can have between these thread blocks.
So this is going to be an important
as we, to understand scalability in your CUDA code.
Now, the thread index and block index are not just one-dimensional,
indices. In CUDA, each dimens-, each thread,
block index can be a 1D, 2D, or 3D variable.
So, each thread index can also be a 1D, 2D,
and 3D. That's why in the previous, slide.
We'll go back to the previous slide here. When we talk about a thread index, I
actually have blockidx.x, because we're only using the first dimension
of the block index variable.
In reality, many applications operate on
two-dimensional data, such as images, three-dimensional
data, such as volume, in a
differential equation solver for computational fluid dynamics.
So that's why it's very convenient to be able to
use 1D, 2D, or 3D block indices and thread indexes.
So that we can map that conveniently to a two-dimensional data or a
three-dimensional data and maintain and keep the program easy to read.
So here I'm showing a two, two-dimensional block structure and,
within each block, a three-dimensional thread structure.
So, when we look at the grid, we see that each block
has two indices, the X and Y indices.
And X is the first one, Y is the second one.
And, so, actually, it's the other way around.
X is the right, the right element and Y is the left element.
So, at the top, we have block 0, 0 and block 0, 1.
So Y equal to 0 for both blocks and
X equal to 0 and 1. And now, the second row
has Y value of 1, and X will vary from 0 to 1.
Obviously, X and Y could vary from 0 to a very large
number, usually in the, tens or even in the hundreds.
So now, we, each dimension in
CUDA can grow to, 600, 2 to the 16th.
Now, when we look at each thread in a block, which I'm showing a
three-dimensional, thread, thread organization within the block.
So I'm expending out block 1, 1 here and I,
I show that, in this toy example, there are 16 threads,
and each thread has a unique three-dimensional ID.
The X ID varies from zero to three, and the Y ID
ranges from zero to one, and Z ID ranges from zero
to one, and that gives us 16 possibilities.
So, as you can see, we can
combine a two-dimensional grid organization with a three-dimensional
block organization, or we can have
three-dimension, three-dimension, two-dimensional, and plus two-dimensional.
So this all depends on the needs of your application.
As we mentioned, this kind of
multidimensional index is very convenient, or we
need to do image processing, or solve
three-dimensional partial differential equations, and so on.
So this concludes the first episode of the introduction to CUDA.
If you'd like to learn more about the basic concepts of data
parallelism and the, the, basic execution model of CUDA, I
would like to encourage you to read Chapter Three of the textbook.
Thank you.